package com.kk.demo.unsface.two.unsafelist;

import java.lang.reflect.InvocationTargetException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Random;

import com.kk.demo.unsface.two.unsafelist.copy.User;

public class UnsafeQuickSoft {

    /**
     * 进行unsafe的集合排序,使用快速排序
    * 方法描述
    * @param array
    * @param left
    * @param right
     * @throws InstantiationException 
    * @创建日期 2016年12月1日
    */
    public <E extends Comparable<E>> void unsafeSort(UnsafeArrayList<E> array,
            int left, int right) throws Exception {

        if (left < right) {
            // int mid = this.partition(array, left, right);
            int mid = this.partitionMemory(array, left, right);

            this.unsafeSort(array, left, mid - 1);

            this.unsafeSort(array, mid + 1, right);
        }

    }

    public <E extends Comparable<E>> int partition(UnsafeArrayList<E> array,
            int left, int right) throws InstantiationException {
        // 获取第一个作业快排的中心节点
        E mid = array.get(left);

        while (left < right) {

            while (left < right && array.get(right).compareTo(mid) >= 0) {
                right--;
            }

            // 当发现右边比左边小时，进行交换
            array.swap(left, right);

            while (left < right && array.get(left).compareTo(mid) <= 0) {
                left++;
            }

            // 当左侧的数据比右侧大时，进宪交换
            array.swap(right, left);
        }

        array.set(left, mid);

        return left;
    }

    public <E extends Comparable<E>> int partitionMemory(
            UnsafeArrayList<E> array, int left, int right) throws Exception {
        // 获取第一个作业快排的中心节点
        int mid = left;

        long objSet = array.getObjectOffset("age");

        while (left < right) {

            while (left < right && array.compleValue(right, mid, objSet) >= 0) {
                right--;
            }

            // 当发现右边比左边小时，进行交换
            array.swap(left, right);

            while (left < right && array.compleValue(left, mid, objSet) <= 0) {
                left++;
            }

            // 当左侧的数据比右侧大时，进宪交换
            array.swap(right, left);
        }

        array.set(left, array.get(mid));

        return left;
    }

    private static final Random RAND = new Random();

    public static void main(String[] args) throws Exception {
        int size = 50000000;

        System.out.println("当前排序大小:" + size);

        UnsafeQuickSoft sort = new UnsafeQuickSoft();

        for (int i = 0; i < 5; i++) {
            sort.testSort(size);
            System.out.println();
        }

        // for (int i = 0; i < size; i++) {
        // System.out.println("当前结果:"+unsafeList.get(i));
        // }

    }

    public void testSort(int size) throws Exception {

        User[] intArray = new User[size];
        
        //进行java数组的初始化及排序
        long arraystartTime = System.currentTimeMillis();
        for (int i = 0; i < size; i++) {
            intArray[i] = new User(i, RAND.nextInt(size));
        }

        Arrays.sort(intArray);

        long arrayEndTime = System.currentTimeMillis();

        System.out.println("Arrays              init+sort:"
                + (arrayEndTime - arraystartTime));

        intArray = null;
        
        
        //进行ArrayList的初始化及排序
        ArrayList<User> arraylist = new ArrayList<>(size);

        long arrayListtartTime = System.currentTimeMillis();

        for (int i = 0; i < size; i++) {
            arraylist.add(new User(i, RAND.nextInt(size)));
        }

        Collections.sort(arraylist);

        long arrayListEndTime = System.currentTimeMillis();

        System.out.println("ArrayList           init+sort:"
                + (arrayListEndTime - arrayListtartTime));

        arraylist = null;
        
        //进行堆外的数据初始化及排序
        UnsafeArrayList<User> unsafeList = new UnsafeArrayList<User>(User.class,
                size);

        UnsafeQuickSoft unsafeSoft = new UnsafeQuickSoft();

        long startTime = System.currentTimeMillis();

        for (int i = 0; i < size; i++) {
            unsafeList.set(i, new User(i, RAND.nextInt(size)));
        }

        unsafeSoft.unsafeSort(unsafeList, 0, size - 1);

        long endTime = System.currentTimeMillis();

        System.out.println(
                "unsafe              init+sort:" + (endTime - startTime));

    }

}
